function insertionSort(arr: number[], left: number, right: number): void {
    for (let i = left + 1; i <= right; i++) {
        let temp = arr[i];
        let j = i - 1;
        while (j >= left && arr[j] > temp) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}

function merge(arr: number[], left: number, mid: number, right: number): void {
    let leftSize = mid - left + 1;
    let rightSize = right - mid;
    let leftArr = new Array<number>(leftSize);
    let rightArr = new Array<number>(rightSize);

    for (let i = 0; i < leftSize; i++) {
        leftArr[i] = arr[left + i];
    }
    for (let j = 0; j < rightSize; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    let i = 0;
    let j = 0;
    let k = left;

    while (i < leftSize && j < rightSize) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < leftSize) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < rightSize) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

export function timsort(arr: number[], minRun: number = 32): number[] {
    const copyArray:number[] = [...arr];
    // const minRun = 32;
    let n = copyArray.length;

    // Step 1: Sort individual subarrays of size minRun
    for (let start = 0; start < n; start += minRun) {
        let end = Math.min(start + minRun - 1, n - 1);
        insertionSort(copyArray, start, end);
    }

    // Step 2: Merge sorted subarrays
    let size = minRun;
    while (size < n) {
        for (let left = 0; left < n; left += size * 2) {
            let mid = Math.min(n - 1, left + size - 1);
            let right = Math.min((left + size * 2 - 1), (n - 1));
            if (mid < right) {
                merge(copyArray, left, mid, right);
            }
        }
        size *= 2;
    }
    return copyArray;
}
